package algorithms.linked;

import java.util.Objects;

/**
 * 单链表
 */
public class LinkedList<T> {
    Node head;
    Node tail;
    int size;
    /**
     * 向链表中添加元素
     *  从头便利到尾部，尾部添加元素
     * @param value
     */
    public void add(T value) {
        // 尾部添加元素
        Node node = new Node(value);
        if (tail == null)
            head = node;
        else
            tail.next = node;
        tail = node;
        ++size;
    }

    /**
     * 向链表中添加元素
     *
     *  从头便利到尾部，尾部添加元素
     * @param value
     */
    public void remove(T value) {
        if(head == null)
            return;
        Node curr = head;
        Node last = head;// 上一个节点
        while (curr.next != null){
            // 元素相等
            if (value.equals(curr.value)) {
                last.next = curr.next;
                curr.next = null;
                break;
            }
            last = curr;
            curr = curr.next;
        }
        --size;
    }

    /**
     * 获取元素个数
     *
     * @return
     */
    public int size() {
        return size ;
    }

    /**
     * 查询链表中是否包含指定元素
     *
     * @param value
     * @return
     */
    public boolean contain(T value) {
        Node curr = head.next;
        Node del = null;// 需要删除的结点
        while (curr.next != null) {
            // 元素相等
            if (value.equals(curr.next.value)) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }

    /**
     * 打印链表中的元素
     */
    public void toPrint() {
        Node curr = head;
        while (curr.next != null) {
            System.out.print(curr.value+" --> ");
            curr = curr.next;
        }
        System.out.print(curr.value);
        System.out.println();
    }
}


/**
 * Node节点
 * @param <T>
 */
class Node<T> {
    Node next;
    T value;

    public Node() {
    }

    public Node(T value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node<?> node = (Node<?>) o;
        return Objects.equals(next, node.next) && Objects.equals(value, node.value);
    }

    @Override
    public int hashCode() {
        return Objects.hash(next, value);
    }

    @Override
    public String toString() {
        return "Node{" +
                "next=" + next +
                ", value=" + value +
                '}';
    }
}
